package com.kevin.Code.Hash;

import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;

/**
 * @author Vinlee Xiao
 * @Classname LFUCache
 * @Description Leetcode 460. LFU 缓存 难度困难 基本没啥思路 细节错误很多
 * @Date 2021/11/7 10:11
 * @Version 1.0
 */
public class LFUCache {

    /**
     * 理清思路
     * 用于记录使用最小的节点
     */
    private int minFeq;
    private int capacity;
    /**
     * 健到节点的映射
     */
    HashMap<Integer, Node> keyToNode;
    /**
     * 存储频度到LinkedHashSet的映射
     */
    HashMap<Integer, LinkedList<Node>> freqTable;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.minFeq = 0;
        keyToNode = new HashMap<Integer, Node>();
        freqTable = new HashMap<Integer, LinkedList<Node>>();
    }

    /**
     * @param key
     * @return
     */
    public int get(int key) {

        //2.如果容量为0
        if (capacity == 0) {
            return -1;
        }

        //1.如果不存在
        if (!keyToNode.containsKey(key)) {
            return -1;
        }

        //否则得到该节点,修改其KeyToNode的值
        Node node = keyToNode.get(key);
        int value = node.getValue();
        int freq = node.getFreq();

        //将频度表中对应的该节点删除
        freqTable.get(freq).remove(node);
        //如果删除的元素为最后一个元素则删除该HashMap
        if (freqTable.get(freq).size() == 0) {
            freqTable.remove(freq);
            //最小的频度增加了1
            if (minFeq == freq) {
                minFeq++;
            }
        }
        LinkedList<Node> newNodeLinkedList = freqTable.getOrDefault(freq + 1, new LinkedList<Node>());
        newNodeLinkedList.offerFirst(new Node(key, value, freq + 1));
        freqTable.put(freq + 1, newNodeLinkedList);
        keyToNode.put(key, freqTable.get(freq + 1).peekFirst());
        return value;
    }

    /**
     * @param key
     * @param value
     */
    public void put(int key, int value) {

        if (capacity == 0) {
            return;
        }

        //如果健不存在，则插入新值
        if (!keyToNode.containsKey(key)) {

            //最久未使用的 使用minFreq得到频度最小的
            if (keyToNode.size() == capacity) {

                Node node = freqTable.get(minFeq).peekLast();
                keyToNode.remove(node.getKey());
                //
                freqTable.get(minFeq).pollLast();
                if (freqTable.get(minFeq).size() == 0) {
                    freqTable.remove(minFeq);
                }
            }

            LinkedList<Node> nodeLinkedList = freqTable.getOrDefault(1, new LinkedList<>());
            nodeLinkedList.offerFirst(new Node(key, value, 1));
            freqTable.put(1, nodeLinkedList);
            keyToNode.put(key, freqTable.get(1).peekFirst());

            minFeq = 1;

        } else {
            //操作和get一样
            Node node = keyToNode.get(key);
            int freq = node.getFreq();

            //根据频度freq得到其对应的链表
            freqTable.get(freq).remove(node);

            if (freqTable.get(freq).size() == 0) {
                freqTable.remove(freq);
                //
                if (minFeq == freq) {
                    minFeq++;
                }
            }
            LinkedList<Node> nodeLinkedList = freqTable.getOrDefault(freq + 1, new LinkedList<Node>());
            nodeLinkedList.offerFirst(new Node(key, value, freq + 1));
            freqTable.put(freq + 1, nodeLinkedList);
            keyToNode.put(key, freqTable.get(freq + 1).peekFirst());


        }
    }

    public static void main(String[] args) {
        LFUCache lfuCache = new LFUCache(2);
        lfuCache.put(0, 0);
        int i = lfuCache.get(0);
        System.out.println(i);

    }
}



